For a given index (address), an ordinary memory generates the registered data stored in that address. On the other hand, a CAM generates the index (address) of a given search (input) data, (See non-patent literature 1, 2) stored in the CAM.
CAMs are used in wide area such as pattern matching, routers for internet, cache for processor, TLB (Translation Lookaside Buffer), data compression, accelerator for a database, neural network, and memory patch.
From their functions, CAMs are usually classified into two types: The first one is a Binary CAM (“BCAM”), and the second one is a ternary CAM (“TCAM”). In the BCAM, each cell stores either 0 or 1. On the other hand, in the TCAM, each cell stores either 0, 1, or *. where, ‘*’ denotes a “don't care”, which matches both 0 and 1.
[Definition 1] (BCAM)
An n-input BCAM table with p registered vectors stores, p different two-valued vectors. We assume that p vectors are stored in the BCAM from the address 1 to the address p, in order. Note that an address of each vector can be represented by m bits. m is given by (1).
[Expression 1]m=┌log2(p+1)┐  (1)The corresponding BCAM function ƒ: {0, 1}n→{0, 1}m satisfies the following condition:
For the given input x, if the same vector exist in the BCAM table, then ƒ(x) produces the CAM address (from 1 to p) that stores the vector x. If no vector in the BCAM table matches to the input x, then the value of ƒ(x) is 0.
(End of Definition)